package com.kongge.algorithm.demo;

import com.kongge.algorithm.list.ListNode;

/**
 * 给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。
 * @author gaoshiqi
 *
 */
public class ListDeleteOnNodeInO1 implements IAlgorithm{

	public void execute() {
		ListNode<Integer> head = ListNode.createList(0, 1, 2, 3, 4);
		ListNode<Integer> node = ListNode.get(head, 4);
		head = deleteNodeInO1(head, node);
		ListNode.printList(head);
		
	}
	
	private ListNode<Integer> deleteNodeInO1(ListNode<Integer> head, ListNode<Integer> node) {
		if (head == null || node == null) {
			return head;
		}
		// 头结点
		if (head == node) {
			return head.next;
		}
		if (node.next != null) {
			// 中间结点
			node.t = node.next.t;
			node.next = node.next.next;
		} else {
			// 尾结点
			ListNode<Integer> tempNode = head;
			while (tempNode.next != null && tempNode.next.next != null) {
				tempNode = tempNode.next;
			}
			if (tempNode.next == node) {
				tempNode.next = null;
			}
		}
		return head;
	}

	
}
